package leet;

import java.util.ArrayList;
import java.util.List;

/**
 * 39. Combination Sum
 * 
 * <pre>
 * Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
 * The same repeated number may be chosen from candidates unlimited number of times.
 * Note:
 *  All numbers (including target) will be positive integers.
 *  The solution set must not contain duplicate combinations.
 * </pre>
 * 
 * @author zhujunbing
 * @date 2019年4月25日
 */
public class Leet0039 {

	public static void main(String[] args) {

		int[] candidates = { 2, 3, 6, 7 };
		int target = 7;

		List<List<Integer>> combinationSum = new Leet0039().combinationSum(candidates, target);

		System.out.println(combinationSum);
	}

	/**
	 * 好像只能遍历，
	 * 
	 * <pre>
	 * 			2 			3    6    7
	 * 		2 3 6 7      3 6 7   6 7   7
	 * </pre>
	 * 
	 * @param candidates
	 * @param target
	 * @return
	 * @date 2019年4月25日
	 */
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		List<List<Integer>> ret = new ArrayList<>();

		if (candidates == null || candidates.length == 0) {
			return ret;
		}

		List<Integer> cur = new ArrayList<>();
		dfs(candidates, 0, target, ret, cur);
		return ret;
	}

	private void dfs(int[] candidates, int start, int target, List<List<Integer>> ret, List<Integer> cur) {

		if (target == 0) {
			ret.add(new ArrayList<>(cur));
			return;
		}

		for (int i = start; i < candidates.length; i++) {
			if (target - candidates[i] >= 0) {
				// 请复用这个cur
				cur.add(candidates[i]);
				dfs(candidates, i, target - candidates[i], ret, cur);
				cur.remove(cur.size() - 1);
			}
		}

	}
}
